package leetcode.code1312;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：8 ms, 在所有 Java 提交中击败了97.60%的用户
//
//内存消耗：43.2 MB, 在所有 Java 提交中击败了5.14%的用户
//
//通过测试用例：57 / 57

//1. 一个字符时
//2. 两个字符时
//3. 三个以及以上时
//+ 两端相等
//+ 两端不等
//
//五种啊，不`药`怀疑。两端不等是两种。

public class Solution implements IDebug {

	public int minInsertions(String s) {
		int len = s.length();
		char[] cs = s.toCharArray();
		int[][] dp = new int[len][len];
		for (int i = len - 2; i >= 0; i--) {
			dp[i][i + 1] = cs[i] == cs[i + 1] ? 0 : 1;
			for (int j = i + 2; j < len; j++) {
				if (cs[i] == cs[j]) {
					dp[i][j] = dp[i + 1][j - 1];
				} else {
					dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
				}
			}
		}
		return dp[0][len - 1];
	}

	@Override
	public void debug1() {
		HelpDebug.compare(0, this.minInsertions("zzazz"));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(2, this.minInsertions("mbadm"));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(5, this.minInsertions("leetcode"));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(0, this.minInsertions("g"));

	}

	public void debug5() {
		HelpDebug.compare(1, this.minInsertions("no"));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();

	}

}
